//: [Previous](@previous)
import Foundation

/*:
 凑零钱问题
 给你 k 种面值的硬币，面值分别为 c1, c2 ... ck ，每种硬 币的数量无限，再给一个总金额 amount ，问你最少需要几枚硬币凑出这个 金额，如果不可能凑出，算法返回 -1 。

 比如说 k = 3 ，面值分别为 1，2，5，总金额 amount = 11 。那么最少需 要 3 枚硬币凑出，即 11 = 5 + 5 + 1。
 */

/*:
 2. 动态规划

 0, n=0
 -1, n<0
 min{dp[n-coin]+1|con<-coins},n>0


 */
func coinChange(coins: [Int], amount: Int) -> Int {
    var dp: [Int] = Array(repeating: amount + 1, count: amount + 1)
    dp[0] = 0
    for i in 0..<dp.count {
        for coin in coins {
            if i - coin < 0 {
                continue
            }
            dp[i] = min(dp[i], 1 + dp[i - coin])
        }
    }
    if dp[amount] == amount + 1 {
        return -1
    }
    return dp[amount]
}

print(coinChange(coins: [1, 5, 10], amount: 11))

//: [Next](@next)
